#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

int e;

struct Node
{
    Node *next[ 4 ], *fail;
    int flag, id;
    Node( ) { id = e++; flag = 0; memset( next, 0, sizeof( next ) ); }
}*head, *q[ 500 ], *fuck[ 500 ];

struct Matrix
{
    int n, m, a[ 200 ][ 200 ];
};

void operator *= ( Matrix &a, const Matrix &b )
{
    Matrix c;
    int i, j, k;
    c.n = a.n; c.m = b.m;
    memset( c.a, 0, sizeof( c.a ) );
    for ( i = 0; i < a.n; i++ )
        for ( j = 0; j < a.m; j++ )
            for ( k = 0; k < b.m; k++ )
                c.a[ i ][ k ] = ( c.a[ i ][ k ] + a.a[ i ][ j ] * b.a[ j ][ k ] ) % 10007;
    a = c;
}

void insert( Node *head, char *s )
{
    Node *p = head;
    int i = 0, t;
    while ( s[ i ] )
    {
        switch( s[ i ] )
        {
            case 'A': t = 0; break;
            case 'T': t = 1; break;
            case 'C': t = 2; break;
            case 'G': t = 3; break;
        }
        if ( !p->next[ t ] )
        {
            p->next[ t ] = new Node;
            fuck[ e - 1 ] = p->next[ t ];
        }
        p = p->next[ t ];
        i++;
    }
    p->flag++;
}

void build_ac( Node *head )
{
    Node *p, *s;
    int i, front = 0, tail = 0;
    head->fail = head;
    q[ tail++ ] = head;
    while ( tail > front )
    {
        p = q[ front++ ];
        for ( i = 0; i < 4; i++ )
            if ( p->next[ i ] )
            {
                if ( p == head ) p->next[ i ]->fail = head;
                else p->next[ i ]->fail = p->fail->next[ i ];
                q[ tail++ ] = p->next[ i ];
                s = p->fail;
                p->next[ i ]->flag |= p->fail->next[ i ]->flag;
            }
            else
            {
                if ( p == head ) p->next[ i ] = head;
                else p->next[ i ] = p->fail->next[ i ];
            }
    }
}

int n, m;
Matrix a, b, c;

void build_matrix( Matrix &a )
{
    int i, j, k;
    for ( i = 0; i < e; i++ )
    {
        for ( j = 0; j < 4; j++ )
        {
            k = fuck[ i ]->next[ j ]->id;
            if ( fuck[ i ]->next[ j ]->flag )
                a.a[ i * 2 ][ k * 2 + 1 ]++;
            else
            {
                a.a[ i * 2 ][ k * 2 ]++;
                a.a[ i * 2 + 1 ][ k * 2 + 1 ]++;
            }
        }
    }
}

void init( )
{
    int i, j;
    char s[ 10 ];
    e = 0;
    head = new Node;
    fuck[ 0 ] = head;
    for ( i = 0; i < m; i++ )
    {
        scanf("%s", s);
        insert( head, s );
    }
    build_ac( head );
    a.n = a.m = e * 2;
    memset( a.a, 0, sizeof( a.a ) );
    build_matrix( a );
    b.n = b.m = e * 2;
    memset( b.a, 0, sizeof( b.a ) );
    for ( i = 0; i < e * 2; i++ ) b.a[ i ][ i ] = 1;
    c.n = 1; c.m = e * 2;
    memset( c.a, 0, sizeof( c.a ) );
    c.a[ 0 ][ 0 ] = 1;
}

void work( )
{
    int p = 1, ans = 1, i;
    while ( p <= n ) p <<= 1;
    p >>= 1;
    while ( p )
    {
        b *= b;
        ans = ans * ans % 10007;
        if ( p & n )
        {
            b *= a;
            ans = ans * 4 % 10007;
        }
        p >>= 1;
    }
    c *= b;
    for ( i = 0; i < e * 2; i++ )
        ans = ( ans + 10007 - c.a[ 0 ][ i ] ) % 10007;
    printf("%d\n", ans);
}

int main( )
{
    while ( scanf("%d%d", &m, &n) != EOF )
    {
        init( );
        work( );
    }
    return 0;
}
